/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/previous-permutation
   @Language: C++
   @Datetime: 16-02-09 08:22
   */

// Method 1, DP, dp[i][j] is first player score, Time 151ms
class Solution {
public:
	/**
	 * @param nums: nums an array of scores
	 * @return: check if player 1 will win
	 */
	bool PredictTheWinner(vector<int> &nums) {
		// write your code here
		int n=nums.size(), sum=0;
		vector<vector<int> > dp(n,vector<int>(n,0));
		sum=dp[0][0]=nums[0];
		for(int i=1; i<n; ++i){
			sum+=nums[i];
			dp[i][i]=nums[i];
			dp[i-1][i]=max(nums[i-1],nums[i]);
		}
		for(int len=2; len<=n; ++len)
			for(int i=0, j=len; j<n; ++i, ++j)
				dp[i][j]=max(nums[i]+min(dp[i+1][j-1],dp[i+2][j])
						,nums[j]+min(dp[i+1][j-1],dp[i][j-2]));
		return dp[0][n-1]>sum/2;
	}
};

// Method 2, DP, dp[i][j] is first player score - second player score, Time 101ms
class Solution {
public:
	/**
	 * @param nums: nums an array of scores
	 * @return: check if player 1 will win
	 */
	bool PredictTheWinner(vector<int> &nums) {
		// write your code here
		int n=nums.size();
		vector<vector<int> > dp(n,vector<int>(n,0));
		for(int i=n; i--; dp[i][i]=nums[i]);
		for(int len=1; len<n; ++len)
			for(int i=0, j=len; j<n; ++i, ++j)
				dp[i][j]=max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1]);
		return dp[0][n-1]>=0;
	}
};
